package com.fh.binarysearch;

/**
 * 74. 搜索二维矩阵
 * @author fuhao
 * @date 2025/10/14 21:51
 */
public class T74SearchMatrix {

    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            // 处理矩阵为空的边界情况[2,6](@ref)
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return false;
            }

            int m = matrix.length;    // 矩阵的行数
            int n = matrix[0].length; // 矩阵的列数

            int left = 0;
            int right = m * n - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2; // 防止溢出
                // 将一维索引mid映射回二维坐标[2,6](@ref)
                int midValue = matrix[mid / n][mid % n];

                if (midValue == target) {
                    return true;
                } else if (midValue < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            // 搜索空间耗尽，未找到目标
            return false;
        }
    }
}
